import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

class MinStack {
    //解法1：构造辅助栈，依次存放出现过的最小值
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> minStack = new ArrayDeque<>();

    //Stack<Integer> minStack = new Stack<>();
    //Stack<Integer> stack = new Stack<>();

    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else {
            if (x <= minStack.peek()) minStack.push(x);
        }
    }
    
    public void pop() {
        int ret = stack.pop();
        if (ret == minStack.peek()) minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

class MinStack2 {
    //解法2：解法1的小优化，和解法1思路差不多 但是效率更好 辅助栈中提前存放一个最大值，每次入栈都放到辅助栈中一个较小值
    Deque<Integer> xStack = new LinkedList<Integer>();
    Deque<Integer> minStack = new LinkedList<Integer>();

    public MinStack2() {
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}

